package class08;

import sun.security.timestamp.TSRequest;

import java.nio.channels.NonWritableChannelException;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class IsBalanced2 {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data){
            value = data;
        }
    }

    public static boolean isBalanced1(Node head){
        boolean[] ans = new boolean[1];
        ans[0] = true;
        process1(head,ans);
        return ans[0];
    }

    public static int process1(Node head,boolean[] ans){
        if (!ans[0]||head==null)
            return -1;
        int leftHeight = process1(head.left,ans);
        int rightHeight = process1(head.right,ans);

        if (Math.abs(leftHeight-rightHeight)>1)
            ans[0] = false;

        int height = Math.max(leftHeight,rightHeight)+1;

        return height;
    }

    public static class Info{
        public boolean isBalanced;
        public int height;

        public Info(boolean i,int h){
            isBalanced = i;
            height = h;
        }
    }

    public static boolean isBalanced2(Node head){
        return process2(head).isBalanced;
    }

    public static Info process2(Node x){
        if (x == null)
            return new Info(true,0);
        Info leftInfo = process2(x.left);
        Info rightInfo = process2(x.right);

        int height = Math.max(leftInfo.height,rightInfo.height)+1;
        boolean isbalanced = true;
        if (!leftInfo.isBalanced||!rightInfo.isBalanced||
        Math.abs(leftInfo.height-rightInfo.height)>1)
            isbalanced = false;
        return new Info(isbalanced,height);
    }

    public static Node generateRandomNode(int maxLevel,int maxValue){
        return generate(1,maxLevel,maxValue);
    }

    public static Node generate(int level,int maxLevel ,int maxValue){
        if (level>maxLevel || Math.random()>0.5)
            return null;
        Node head = new Node((int)(Math.random()*maxValue));
        head.left = generate(level+1,maxLevel,maxValue);
        head.right = generate(level+1,maxLevel,maxValue);
        return head;
    }

    public static void main(String[] args) {
        int maxLevel = 10;
        int maxValue = 100;
        int testTime =100000;
        for (int i=0;i< testTime;i++){
            Node head = generateRandomNode(maxLevel,maxValue);
            if (isBalanced1(head)!=isBalanced2(head))
                System.out.println("Oops!");
        }

        System.out.println("finish!");
    }
}
